1538D - Another Problem About Dividing Numbers - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define f(i, a, b) for (ll i = a; i < b; i++)
#define fr(i, a, b) for (ll i = b - 1; i >= a; i--)
#define fa(x) for (auto ele : x)

#define all(x) (x).begin(), (x).end()
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ppiii pair<pair<int, int>, int>

#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vs vector<string>
#define v(ele) vector<ele>

#define sei set<int>
#define sel set<ll>
#define ses set<string>
#define sec set<char>
#define se(ele) set<ele>

#define mii map<int, int>
#define mll map<ll, ll>
#define m(e1, e2) map<e1, e2>
#define mipii map<int, pii>
#define mcpii map<char, pii>
#define mcpci map<char, pair<char, int>>
#define mpiii map<pair<char, int>, int>
#define mic map<int, char>
#define mci map<char, int>
#define mcsei map<char, sei>
#define mlsel map<ll, sel>
#define mcvi map<char, vi>
#define mci map<char, int>
#define msi map<string, int>
#define misei map<int, sei>
#define mlvl map<ll, vl>
#define mivi map<int, vi>
#define mlpll map<ll, pll>
#define mplll map<pll, ll>

#define qi queue<int>
#define ql queue<ll>
#define qpii queue<pair<int, int>>

const ll mod = 1e9 + 7;
const ll INF = 1e16;
const ll NEG_INF = LONG_LONG_MIN;

const ll N = 31634;
// const int N = 51;

set<int> primes;
bool com[N];
void seive()
{
    f(i, 2, N)
    {
        if (com[i] == 0)
        {
            primes.insert(i);
            for (int j = i * i; j < N && j > 0; j += i)
            {
                com[j] = 1;
            }
        }
    }
}

void YN(bool possible)
{
    if (possible)
    {
        cout << "YES\n";
    }
    else
    {
        cout << "NO\n";
    }
}

void count(int n, int &k)
{
    if (k < 1)
    {
        return;
    }
    // int ans = 0;
    auto it = primes.begin();
    while (it != primes.end() && *it < sqrt(n) + 1)
    {
        int i = *it;
        it++;
        if (n % i == 0)
        {
            while (n % i == 0)
            {
                // ans++;
                k--;
                n /= i;
                if (k < 1)
                {
                    return;
                }
            }
        }
        if (k < 1)
        {
            return;
        }
    }
    if (n != 1)
    {
        // ans++;
        k--;
    }
    // return ans;
    return;
}

void solve()
{
    int a, b, k;
    cin >> a >> b >> k;
    if (k > 70)
    {
        YN(0);
        return;
    }
    int g = __gcd(a, b);
    int mini = 1 + (g != min(a, b));
    bool p1 = (a != b || k > 1), p2 = (k >= mini);
    count(a, k);
    count(b, k);
    YN(k < 1 && p1 && p2);
    return;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    int t = 1;
    seive();
    cin >>
        t;
    while (t--)
    {
        solve();
    }
    return 0;
}